#include<iostream>
#include<vector>
#include<queue>

using namespace std;


class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> answer;
        int n = nums.size();
        int cur = 0;
        while (cur < n) {
            int v = cur + 1;
            while (v < n) {
                int left = v + 1;
                int right = n - 1;

                long long part = (long long)target - nums[cur] - nums[v];
                while (left < right) {
                    long long sum = nums[left] + nums[right];
                    if (sum > part) {
                        right--;
                    }
                    else if (sum < part) {
                        left++;
                    }
                    else {
                        answer.push_back(
                            { nums[cur], nums[v], nums[left], nums[right] });
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    }
                }
                v++;
                while (v < n && nums[v] == nums[v - 1]) {
                    v++;
                }
            }
            cur++;
            while (cur < n && nums[cur] == nums[cur - 1]) {
                cur++;
            }
        }
        return answer;
    }
};

int main()
{
    Solution s;
    vector<int> h = { -1,-1,0,1};
    return 0;
}